package lc_3224_使差值相等的最少数组改动次数;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class Solution {

    /**
     * @param nums
     * @param k
     * @return
     */
    public int minChanges(int[] nums, int k) {
        TreeMap<Integer, Integer> tm = new TreeMap<>();
        Map<Integer, Integer> mp = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i < n / 2; i++) {
            int key = Math.max(Math.max(nums[i], k - nums[i]), Math.max(nums[n - i - 1], k - nums[n - i - 1]));
            tm.merge(key, 1, Integer::sum);
            mp.merge(Math.abs(nums[i] - nums[n - i - 1]), 1, Integer::sum);
        }
        for (Map.Entry<Integer, Integer> entry : tm.entrySet()) {
            tm.compute(entry.getKey(),
                    (a, b) -> (tm.floorEntry(entry.getKey() - 1) == null ? 0
                            : tm.floorEntry(entry.getKey() - 1).getValue()) + entry.getValue());
        }
        int ans = n / 2;
        for (Map.Entry<Integer, Integer> entry : mp.entrySet()) {
            Map.Entry<Integer, Integer> e = tm.floorEntry(entry.getKey() - 1);
            int cur = e == null ? 0 : e.getValue();
            // ans = Math.min(ans, cur * 2 + n / 2 - cur - entry.getValue());
            ans = Math.min(ans, cur + n / 2 - entry.getValue());
        }

        return ans;
    }

    public static void main(String[] args) {
        Solution so = new Solution();
        so.minChanges(new int[] { 1, 0, 1, 2, 4, 3 }, 4);
    }

}